package org.algorithm.Kmp;

public class KMPAlgorithm {
    private int[] buildPartialMatchTable(String pattern) {
        int patternLength = pattern.length();
        int[] lps = new int[patternLength]; // longest proper prefix which is also suffix
        int j = 0; // length of the previous longest prefix suffix

        lps[0] = 0; // lps[0] is always 0

        // 计算lps数组的其余部分
        for (int i = 1; i < patternLength; ) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                lps[i] = j + 1;
                j++;
                i++;
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // KMP搜索算法
    public int search(String text, String pattern) {
        int[] lps = buildPartialMatchTable(pattern);
        int i = 0; // index for text[]
        int j = 0; // index for pattern[]

        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == pattern.length()) {
                return i - j; // 找到匹配，返回模式串在文本串中的起始索引
            }

            // 发生不匹配时，根据部分匹配表调整位置
            else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) j = lps[j - 1];
                else i = i + 1;
            }
        }

        return -1; // 未找到匹配，返回-1
    }

    public static void main(String[] args) {
        KMPAlgorithm kmp = new KMPAlgorithm();
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int result = kmp.search(text, pattern);
        if (result == -1) {
            System.out.println("Pattern not found");
        } else {
            System.out.println("Pattern found at index: " + result);
        }
    }
}
